/****************************************************************
 * description      :    graph.h c version                                              
 * author           :    Wang Mingyin
 * time             :    August 1th ~ August 2th, 2013
 ****************************************************************/

#ifndef _GRAPH_C_H_
#define _GRAPH_C_H_

#include <string.h>
#include "../cmn/cmn.h"

//extern struct Node;
typedef struct Nodeptr {
		struct Node    *ptr;
		struct Nodeptr *next;
} Nodeptr;

typedef Nodeptr DBlockType;
typedef int node_id;
typedef node_id BlockType;
//#define NULL 0

/*********************************************************
 *            Block                                      *
 * example:   Block *b = (Block*)malloc(sizeof(Block));  *
 *                       Func_Block(b);                  *
 *                       b->BlockConstruct(b, size, 0);  *
 *********************************************************/
typedef struct BlockItem {
	BlockType   *current, *last;
	struct BlockItem *next;
	BlockType	data[1];
} BlockItem;

typedef struct Block {
	int		block_size;
	BlockItem	*first;
	BlockItem	*last;

	BlockItem	*scan_current_block;
	BlockType	*scan_current_data;
	void	(*error_function)(char *); 

	/* Constructor. Arguments are the block size and
	   (optionally) the pointer to the function which
	   will be called if allocation failed; the message
	   passed to this function is "Not enough memory!" */
	void (*BlockConstruct) (struct Block *b, int size, void (*err_func)(char *));

	/* Destructor. Deallocates all items added so far */
	void (*BlockDeconstruct) (struct Block *b);

	/* Allocates 'num' consecutive items; returns pointer
	   to the first item. 'num' cannot be greater than the
	   block size since items must fit in one block */
	BlockType *(*New)(struct Block *b, int num);

	/* Returns the first item (or NULL, if no items were added) */
	BlockType *(*ScanFirst)(struct Block *b);

	/* Returns the next item (or NULL, if all items have been read)
	   Can be called only if previous ScanFirst() or ScanNext()
	   call returned not NULL. */
	BlockType *(*ScanNext)(struct Block *b);

	/* Marks all elements as empty */
	void (*Reset)(struct Block *b);
} Block;

void Block_BlockConstruct(Block *b, int size, void (*err_func)(char *));
void Block_BlockDeconstruct(struct Block *b);
BlockType* Block_New(Block *b, int num);
BlockType *Block_ScanFirst(struct Block *b);
BlockType *Block_ScanNext(struct Block *b);
void Block_Reset(Block *b);
void Funcs_Block(Block *b);

/************************************************************
 *            DBlock                                        *
 * example:   DBlock *db = (DBlock*)malloc(sizeof(DBlock)); *
 *                       Func_DBlock(db);                   *
 *                       db->DBlockConstruct(db, size, 0);  *
 ************************************************************/
typedef union DBlockInnerItem {
	DBlockType			t;
	union DBlockInnerItem	*next_free;
} DBlockInnerItem;

typedef struct DBlockItem {
	struct DBlockItem *next;
	DBlockInnerItem	data[1];
} DBlockItem;

typedef struct DBlock {
	int			block_size;
	DBlockItem		*first;
	DBlockInnerItem	*first_free; 
	void	(*error_function)(char *);

	/* Constructor. Arguments are the block size and
	   (optionally) the pointer to the function which
	   will be called if allocation failed; the message
	   passed to this function is "Not enough memory!" */
	void (*DBlockConstruct)(struct DBlock *db, int size, void (*err_func)(char *));

	/* Destructor. Deallocates all items added so far */
	void (*DBlockDeconstruct)(struct DBlock *db);

	/* Allocates one item */
	DBlockType* (*New)(struct DBlock *db);

	/* Deletes an item allocated previously */
	void (*Delete)(struct DBlock *db, DBlockType *t);
} DBlock;

void DBlock_DBlockConstruct(DBlock *db, int size, void (*err_func)(char *));
void DBlock_DBlockDeconstruct(struct DBlock *db);
DBlockType* DBlock_New(struct DBlock *db);
void DBlock_Delete(struct DBlock *db, DBlockType *t);
void Func_DBlock(DBlock *db);


typedef float captype; // captype: type of edge capacities (excluding t-links)
typedef float tcaptype; // tcaptype: type of t-links (edges between nodes and terminals)
typedef float flowtype; // flowtype: type of total flow
typedef int node_id;

/*
	special constants for node->parent
*/
#define TERMINAL ( (struct Arc *) 1 )		/* to terminal */
#define ORPHAN   ( (struct Arc *) 2 )		/* orphan */
#define INFINITE_D ((int)(((unsigned)-1)/2))		/* infinite distance to the terminal */

struct Arc;
struct Node;


#define NODEPTR_BLOCK_SIZE  128

typedef enum {
		SOURCE	= 0,
		SINK	= 1
} TermType; // terminals 


typedef struct Node {
	struct Arc	*first;		// first outcoming arc

	struct Arc	*parent;	// node's parent
	struct Node *next;		// pointer to the next active node
	//   (or to itself if it is the last node in the list)
	int			TS;			// timestamp showing when DIST was computed
	int			DIST;		// distance to the terminal
	int			is_sink : 1;	// flag showing whether the node is in the source or in the sink tree (if parent!=NULL)
	int			is_marked : 1;	// set by mark_node()
	int			is_in_changed_list : 1; // set by maxflow if 

	tcaptype	tr_cap;		// if tr_cap > 0 then tr_cap is residual capacity of the arc SOURCE->node
	// otherwise         -tr_cap is residual capacity of the arc node->SINK 
} Node;

struct Arc {
	struct Node		*head;		// node the arc points to
	struct Arc		*next;		// next arc with the same originating node
	struct Arc		*sister;	// reverse arc

	captype		    r_cap;		// residual capacity
};

typedef struct Arc* Arc_id;


/*********************************************************
 *                                                    Graph                                                                *
 * example:   Graph *g = (Graph*)malloc(sizeof(Graph));
 *                       Func_Graph(g);
 *                       g->DBlockConstruct(g, node_num, edge_num, NULL);
 *********************************************************/
typedef struct Graph {

	// internal variables and functions
	Node				*nodes, *node_last, *node_max; // node_last = nodes+node_num, node_max = nodes+node_num_max;
	struct Arc					*arcs, *arc_last, *arc_max; // arc_last = arcs+2*edge_num, arc_max = arcs+2*edge_num_max;

	int                   node_num;

	DBlock          *nodeptr_block; 
	//DBlock<nodeptr>		*nodeptr_block;

	void	(*error_function)(char *);	// this function is called if a error occurs,
										// with a corresponding error message
										// (or exit(1) is called if it's NULL)

	flowtype			flow;		// total flow

	// reusing trees & list of changed pixels
	int					   maxflow_iteration; // counter
	//Block<node_id>		*changed_list;
	Block                *changed_list;

	/////////////////////////////////////////////////////////////////////////

	Node				*queue_first[2], *queue_last[2];	// list of active nodes
	Nodeptr				*orphan_first, *orphan_last;		// list of pointers to orphans
	int					TIME;								// monotonically increasing global counter


	void (*reallocate_nodes)(struct Graph *g, int num); // num is the number of new nodes
	void (*reallocate_arcs)(struct Graph *g);

	/////////////////////////////////////////////////////////////////////////
	//                     BASIC INTERFACE FUNCTIONS                       //
    //              (should be enough for most applications)               //
	/////////////////////////////////////////////////////////////////////////
	// Constructor. 
	// The first argument gives an estimate of the maximum number of nodes that can be added
	// to the graph, and the second argument is an estimate of the maximum number of edges.
	// The last (optional) argument is the pointer to the function which will be called 
	// if an error occurs; an error message is passed to this function. 
	// If this argument is omitted, exit(1) will be called.
	//
	// IMPORTANT: It is possible to add more nodes to the graph than node_num_max 
	// (and node_num_max can be zero). However, if the count is exceeded, then 
	// the internal memory is reallocated (increased by 50%) which is expensive. 
	// Also, temporarily the amount of allocated memory would be more than twice than needed.
	// Similarly for edges.
	// If you wish to avoid this overhead, you can download version 2.2, where nodes and edges are stored in blocks.
	void (*GraphConstruct)(struct Graph *g, int node_num_max, int edge_num_max, void (*err_func)(char *));

	// Destructor
	void (*GraphDeconstruct)(struct Graph *g);

	// Adds node(s) to the graph. By default, one node is added (num=1); then first call returns 0, second call returns 1, and so on. 
	// If num>1, then several nodes are added, and node_id of the first one is returned.
	// IMPORTANT: see note about the constructor 
	node_id (*add_node)(struct Graph *g, int num);  //TODO default value

	// Adds a bidirectional edge between 'i' and 'j' with the weights 'cap' and 'rev_cap'.
	// IMPORTANT: see note about the constructor 
	void (*add_edge)(struct Graph *g, node_id i, node_id j, captype cap, captype rev_cap);

	// Adds new edges 'SOURCE->i' and 'i->SINK' with corresponding weights.
	// Can be called multiple times for each node.
	// Weights can be negative.
	// NOTE: the number of such edges is not counted in edge_num_max.
	//       No internal memory is allocated by this call.
	void (*add_tweights)(struct Graph *g, node_id i, tcaptype cap_source, tcaptype cap_sink);

	// Computes the maxflow. Can be called several times.
	// FOR DESCRIPTION OF reuse_trees, SEE mark_node().
	// FOR DESCRIPTION OF changed_list, SEE remove_from_changed_list().
	flowtype (*maxflow)(struct Graph *g, int reuse_trees, Block *changed_list); //TODO default value

	// After is computed, this function returns to which
	// segment the node 'i' belongs (Graph<captype,tcaptype,flowtype>::SOURCE or Graph<captype,tcaptype,flowtype>::SINK).
	//
	// Occasionally there may be several minimum cuts. If a node can be assigned
	// to both the source and the sink, then default_segm is returned.
	TermType (*what_segment)(struct Graph *g, node_id i, TermType default_segm);  //TODO default value

	
	//////////////////////////////////////////////
	//       ADVANCED INTERFACE FUNCTIONS       //
	//      (provide access to the graph)       //
	//////////////////////////////////////////////

		////////////////////////////
	// 1. Reallocating graph. //
	////////////////////////////

	// Removes all nodes and edges. 
	// After that functions add_node() and add_edge() must be called again. 
	//
	// Advantage compared to deleting Graph and allocating it again:
	// no calls to delete/new (which could be quite slow).
	//
	// If the graph structure stays the same, then an alternative
	// is to go through all nodes/edges and set new residual capacities
	// (see functions below).
	void (*reset)(struct Graph *g);

		////////////////////////////////////////////////////////////////////////////////
	// 2. Functions for getting pointers to arcs and for reading graph structure. //
	//    NOTE: adding new arcs may invalidate these pointers (if reallocation    //
	//    happens). So it's best not to add arcs while reading graph structure.   //
	////////////////////////////////////////////////////////////////////////////////

	// The following two functions return arcs in the same order that they
	// were added to the graph. NOTE: for each call add_edge(i,j,cap,cap_rev)
	// the first arc returned will be i->j, and the second j->i.
	// If there are no more arcs, then the function can still be called, but
	// the returned arc_id is undetermined.
	Arc_id (*get_first_arc)(struct Graph *g);
	Arc_id (*get_next_arc)(struct Graph *g, Arc_id a);

	// other functions for reading graph structure
	int (*get_node_num)(struct Graph *g);
	int (*get_arc_num)(struct Graph *g);
	void (*get_arc_ends)(struct Graph *g, Arc_id a, node_id *i, node_id *j); // returns i,j to that a = i->j

	///////////////////////////////////////////////////
	// 3. Functions for reading residual capacities. //
	///////////////////////////////////////////////////

	// returns residual capacity of SOURCE->i minus residual capacity of i->SINK
	tcaptype (*get_trcap)(struct Graph *g, node_id i); 
	// returns residual capacity of arc a
	captype (*get_rcap)(struct Graph *g, struct Arc *a);

	/////////////////////////////////////////////////////////////////
	// 4. Functions for setting residual capacities.               //
	//    NOTE: If these functions are used, the value of the flow //
	//    returned by maxflow() will not be valid!                 //
	/////////////////////////////////////////////////////////////////

	void (*set_trcap)(struct Graph *g, node_id i, tcaptype trcap); 
	void (*set_rcap)(struct Graph *g, struct Arc *a, captype rcap);

	////////////////////////////////////////////////////////////////////
	// 5. Functions related to reusing trees & list of changed nodes. //
	////////////////////////////////////////////////////////////////////

	// If flag reuse_trees is true while calling maxflow(), then search trees
	// are reused from previous maxflow computation. 
	// In this case before calling maxflow() the user must
	// specify which parts of the graph have changed by calling mark_node():
	//   add_tweights(i),set_trcap(i)    => call mark_node(i)
	//   add_edge(i,j),set_rcap(a)       => call mark_node(i); mark_node(j)
	//
	// This option makes sense only if a small part of the graph is changed.
	// The initialization procedure goes only through marked nodes then.
	// 
	// mark_node(i) can either be called before or after graph modification.
	// Can be called more than once per node, but calls after the first one
	// do not have any effect.
	// 
	// NOTE: 
	//   - This option cannot be used in the first call to maxflow().
	//   - It is not necessary to call mark_node() if the change is ``not essential'',
	//     i.e. sign(trcap) is preserved for a node and zero/nonzero status is preserved for an arc.
	//   - To check that you marked all necessary nodes, you can call maxflow(false) after calling maxflow(true).
	//     If everything is correct, the two calls must return the same value of flow. (Useful for debugging).
	void (*mark_node)(struct Graph *g, node_id i);

	// If changed_list is not NULL while calling maxflow(), then the algorithm
	// keeps a list of nodes which could potentially have changed their segmentation label.
	// Nodes which are not in the list are guaranteed to keep their old segmentation label (SOURCE or SINK).
	// Example usage:
	//
	//		typedef Graph<int,int,int> G;
	//		G* g = new Graph(nodeNum, edgeNum);
	//		Block<G::node_id>* changed_list = new Block<G::node_id>(128);
	//
	//		... // add nodes and edges
	//
	//		g->maxflow(); // first call should be without arguments
	//		for (int iter=0; iter<10; iter++)
	//		{
	//			... // change graph, call mark_node() accordingly
	//
	//			g->maxflow(true, changed_list);
	//			G::node_id* ptr;
	//			for (ptr=changed_list->ScanFirst(); ptr; ptr=changed_list->ScanNext())
	//			{
	//				G::node_id i = *ptr; assert(i>=0 && i<nodeNum);
	//				g->remove_from_changed_list(i);
	//				// do something with node i...
	//				if (g->what_segment(i) == G::SOURCE) { ... }
	//			}
	//			changed_list->Reset();
	//		}
	//		delete changed_list;
	//		
	// NOTE:
	//  - If changed_list option is used, then reuse_trees must be used as well.
	//  - In the example above, the user may omit calls g->remove_from_changed_list(i) and changed_list->Reset() in a given iteration.
	//    Then during the next call to maxflow(true, &changed_list) new nodes will be added to changed_list.
	//  - If the next call to maxflow() does not use option reuse_trees, then calling remove_from_changed_list()
	//    is not necessary. ("changed_list->Reset()" or "delete changed_list" should still be called, though).
	void (*remove_from_changed_list)(struct Graph *g, node_id i); 

	// functions for processing active list
	void (*set_active)(struct Graph *g, Node *i);
	Node* (*next_active)(struct Graph *g);

	// functions for processing orphans list
	void (*set_orphan_front)(struct Graph *g, Node* i); // add to the beginning of the list
	void (*set_orphan_rear)(struct Graph *g, Node* i);  // add to the end of the list

	void (*add_to_changed_list)(struct Graph *g, Node* i);

	void (*maxflow_init)(struct Graph *g);             // called if reuse_trees == false
	void (*maxflow_reuse_trees_init)(struct Graph *g); // called if reuse_trees == true
	void (*augment)(struct Graph *g, struct Arc *middle_arc);
	void (*process_source_orphan)(struct Graph *g, Node *i);
	void (*process_sink_orphan)(struct Graph *g, Node *i);

	void (*test_consistency)(struct Graph *g, Node* current_node); // debug function //TODO default value
} Graph;

//basic
void Graph_reallocate_nodes(struct Graph *g, int num);
void Graph_reallocate_arcs(struct Graph *g);

void Graph_GraphConstruct(struct Graph *g, int node_num_max, int edge_num_max, void (*err_func)(char *));
void Graph_GraphDeconstruct(struct Graph *g);

node_id Graph_add_node(struct Graph *g, int num);
void Graph_add_edge(struct Graph *g, node_id _i, node_id _j, captype cap, captype rev_cap);
void Graph_add_tweights(struct Graph *g, node_id i, tcaptype cap_source, tcaptype cap_sink);
TermType Graph_what_segment(struct Graph *g, node_id i, TermType default_segm);
//advanced
void Graph_reset(struct Graph *g);
Arc_id Graph_get_first_arc(struct Graph *g);
Arc_id Graph_get_next_arc(struct Graph *g, Arc_id a);
int Graph_get_node_num(struct Graph *g);
int Graph_get_arc_num(struct Graph *g);
void Graph_get_arc_ends(struct Graph *g, Arc_id a, node_id *i, node_id *j);
tcaptype Graph_get_trcap(struct Graph *g, node_id i);
captype Graph_get_rcap(struct Graph *g, struct Arc *a);
void Graph_set_trcap(struct Graph *g, node_id i, tcaptype trcap);
void Graph_set_rcap(struct Graph *g, struct Arc *a, captype rcap);
void Graph_mark_node(struct Graph *g, node_id _i);
void Graph_remove_from_changed_list(struct Graph *g, node_id i);

void Graph_set_active(struct Graph *g, Node *i);
Node* Graph_next_active(struct Graph *g);
void Graph_set_orphan_front(struct Graph *g, Node* i);
void Graph_set_orphan_rear(struct Graph *g, Node* i);
void Graph_add_to_changed_list(struct Graph *g, Node* i);

void Graph_maxflow_init(struct Graph *g);             // called if reuse_trees == false
void Graph_maxflow_reuse_trees_init(struct Graph *g); // called if reuse_trees == true
void Graph_augment(struct Graph *g, struct Arc *middle_arc);
void Graph_process_source_orphan(struct Graph *g, Node *i);
void Graph_process_sink_orphan(struct Graph *g, Node *i);
flowtype Graph_maxflow(struct Graph *g, int reuse_trees, Block *changed_list);
void Graph_test_consistency(struct Graph *g, Node* current_node); // debug function

void Func_Graph(struct Graph *g);
void Graph_GraphConstruct(struct Graph *g, int node_num_max, int edge_num_max, void (*err_func)(char *));
void Graph_GraphDeconstruct(struct Graph *g);
void Graph_reallocate_nodes(struct Graph *g, int num);
void Graph_reallocate_arcs(struct Graph *g);
//void Graph_reset(struct Graph *g);

/****************************************************************
 ******************           Graphcut         ******************
 ****************************************************************/
void delete_graph();
void create_graph(int node_num, int edge_num);
void graph_add_node();
void graph_add_tweights(int node_index, float weight_source, float weight_sink);
void graph_add_edge(int node1_index, int node2_index, float weight_1to2, float weight_2to1);
float graph_max_flow();
int graph_get_segment(int node_index);

#endif
